package club.xiaojiawei.back;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 5/21/22 5:05 PM
 * @question 78. 子集
 * @description 给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
 * 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
 */
public class Subsets78 {

    public static void main(String[] args) {
        Subsets78 test = new Subsets78();
        List<List<Integer>> result = test.subsets(new int[]{1, 2, 3});
        System.out.println(result);
    }

    /**
     * 递归回溯
     * @param nums
     * @return
     */
    public List<List<Integer>> subsets(int[] nums) {
        result.add(new ArrayList<>());
        recursion(nums, 0);
        return result;
    }

    List<List<Integer>> result = new ArrayList<>();

    List<Integer> temp = new ArrayList<>();

    public void recursion(int[] nums, int startIndex){
        if (startIndex == nums.length){
            return;
        }
        for (int i = startIndex; i < nums.length; i++){
            temp.add(nums[i]);
            result.add(new ArrayList<>(temp));
            recursion(nums, i + 1);
            temp.remove(temp.size() - 1);
        }
    }

    List<Integer> t = new ArrayList<Integer>();
    List<List<Integer>> ans = new ArrayList<List<Integer>>();

    /**
     * 官方-迭代+二进制
     * @param nums
     * @return
     */
    public List<List<Integer>> subsets2(int[] nums) {
        int n = nums.length;
        for (int mask = 0; mask < (1 << n); ++mask) {
            t.clear();
            for (int i = 0; i < n; ++i) {
                if ((mask & (1 << i)) != 0) {
                    t.add(nums[i]);
                }
            }
            ans.add(new ArrayList<Integer>(t));
        }
        return ans;
    }

    /**
     * dp
     * @param nums
     * @return
     */
    public List<List<Integer>> subsets3(int[] nums) {
        List<List<Integer>> lists = new ArrayList<>(); // 解集
        lists.add(new ArrayList<Integer>()); // 首先将空集加入解集中
        for(int i = 0; i < nums.length; i++){
            int size = lists.size(); // 当前子集数
            for(int j = 0; j < size; j++){ 
                List<Integer> newList = new ArrayList<>(lists.get(j));// 拷贝所有子集
                newList.add(nums[i]); // 向拷贝的子集中加入当前数形成新的子集
                lists.add(newList); // 向lists中加入新子集
            }
        }
        return lists;
    }

}
